Longest string chain

Time: O(NxL^2); Space: O(NxL); medium

Given a list of words, each word consists of English lowercase letters.

Let’s say word1 is a predecessor of word2 if and only if we can add exactly one letter anywhere in word1 to make it equal to word2. For example, “abc” is a predecessor of “abac”.

A word chain is a sequence of words [word_1, word_2, …, word_k] with k >= 1, where word_1 is a predecessor of word_2, word_2 is a predecessor of word_3, and so on.

Return the longest possible length of a word chain with words chosen from the given list of words.

Example 1:

Input: words = [“a”,“b”,“ba”,“bca”,“bda”,“bdca”]

Output: 4

Explanation:

  • One of the longest word chain is “a”,“ba”,“bda”,“bdca”.

Constraints:

  • 1 <= len(words) <= 1000

  • 1 <= len(words[i]) <= 16

  • words[i] only consists of English lowercase letters.

Hints:

  1. Instead of adding a character, try deleting a character to form a chain in reverse.

  2. For each word in order of length, for each word2 which is word with one character removed, length[word2] = max(length[word2], length[word] + 1).

1. Dynamic programming [O(NxL^2), O(NxL)]

[1]:

import collections

class Solution1(object):
    """
    Time: O(N*L^2)
    Space: O(N*L)
    """
    def longestStrChain(self, words):
        """
        :type words: List[str]
        :rtype: int
        """
        words.sort(key=len)
        dp = collections.defaultdict(int)

        for w in words:
            for i in range(len(w)):
                dp[w] = max(dp[w], dp[w[:i]+w[i+1:]]+1)

        return max(dp.itervalues())

[2]:

s = Solution1()

words = ["a","b","ba","bca","bda","bdca"]
assert s.longestStrChain(words) == 4